class Solution:
    def tribonacci(self, n: int) -> int:

        # 处理特殊情况（初始值）
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1

        # 初始化前3个泰波那契数
        a, b, c = 0, 1, 1  # 分别对应 T0, T1, T2

        # 从 T3 计算到 Tn
        for i in range(3, n + 1):
            d = a + b + c  # 当前值 = 前3个值的和
            # 更新前3个值（向后移动一位）
            a, b, c = b, c, d

        return c
S = Solution()

print(S.tribonacci(4))
